class BinaryTree(object):

    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None

root1 = BinaryTree(1)
root2 = BinaryTree(2)
root3 = BinaryTree(3)
root4 = BinaryTree(4)
root5 = BinaryTree(5)
root6 = BinaryTree(6)
root7 = BinaryTree(7)
root8 = BinaryTree(8)
root9 = BinaryTree(9)
root10 = BinaryTree(10)
root11 = BinaryTree(11)
root12 = BinaryTree(12)

root1.left = root2
root1.right = root8

root2.left = root3
root2.right = root6

root3.left = root4
root3.right = root5

root8.left = root9

root6.left = root7


def dfs(root:BinaryTree):
    print(root.root)
    if root.left:
        dfs(root.left)
    if root.right:
        dfs(root.right)

dfs(root1)

